L’analisi mediante logica proposizionale ha vantaggi e svantaggi.
Vantaggi
Si tratta di un’analisi relativamente semplice ed è implementabile su un computer: i connettivi diventano porte logiche, per controllare la validità di una proposizione/ragionamento basta calcolarne la tavola di verità (che è un processo algoritmico finito, quindi implementabile mediante un programma informatico, anche se molto dispendioso in termini di tempo/memoria), e così via.
Svantaggi
Si tratta di un’analisi molto grossolana!! Per esempio non permette di verificare la correttezza di un ragionamento come
Chi studia passa l’esame. Gli amici di Carlo hanno studiato, quindi passano l’esame.
Per analizzare il ragionamento precedente abbiamo bisogno di strutture linguistiche più complesse:
connettivi e parentesi: come in logica proposizionale;
variabili \(x\), \(y\), …: indicano generici elementi dell’universo del discorso;
quantificatori \(\forall\) e \(\exists\): vengono usati per indicare per quali \(x\) valga o meno una certa affermazione (per tutti, per qualcuno, …);
simboli di relazione \(P\), \(Q\), …: vengono usati per esprimere sia proprietà di singoli elementi (\(S(x)\) per “\(x\) studia”, \(P(x)\) per “\(x\) passa l’esame”) che relazioni tra elementi (\(A(x,y)\) per “\(x\) e \(y\) sono amici”);
simboli di costante \(a\), \(b\), …: vengono usati per nominare particolari elementi dell’universo del discorso (\(c\) per “Carlo”);
simboli di funzione \(f\), \(g\), …: vengono utilizzati per rappresentare costrutti che si comportano come funzioni (\(f(x)\) per “il padre di \(x\)”).
Chi studia passa l’esame. Gli amici di Carlo hanno studiato, quindi passano l’esame.
diventa allora \[\Big( \forall x (S(x) \to P(x)) \wedge \forall x (A(x,c) \to S(x)) \Big ) \to \forall x (A(x,c) \to P(x)).\]
La logica del prim’ordine permette di stabilire che questo ragionamento è corretto, indipendentemente dall’interpretazione dei simboli \(S,P,A,c\)!
Per esempio, se interpretiamo \(S(x)\) come “\(x\) è tedesco”, \(P(x)\) come “\(x\) è biondo”, \(A(x,y)\) come “\(x\) è cugino di \(y\)” e \(c\) come “Claudio”, il ragionamento risultante, ovvero
Tutti i tedeschi sono biondi. I cugini di Claudio sono tedeschi, quindi sono biondi.
rimarrebbe comunque corretto.
Una cosa analoga accade in matematica. Se vogliamo scrivere che in \(\mathbb{Z}\) è sempre possibile eseguire la sottrazione tra due numeri, utilizzeremo un simbolo di funzione binaria \(+\) (che di solito rappresenta la somma) e scriveremo \[\forall x \forall y \exists z (z + y = x ).\] A differenza del caso precedente, la validità di questa formula dipende però dal contesto:
se ci poniamo in \(\mathbb{Z}\) ed effettivamente interpretiamo \(+\) come la somma, allora la formula è vera ed asserisce che esiste sempre la differenza \(z\) di due numeri dati \(x\) e \(y\);
se interpretiamo \(+\) come somma ma restringiamo l’attenzione ad un diverso universo del discorso, ad esempio all’insieme dei numeri naturali \(\mathbb{N}\), allora la formula può diventare falsa;
lo stesso accade se continuiamo a considerare \(\mathbb{Z}\) come universo del discorso ma interpretiamo il simbolo \(+\) in maniera differente, ad esempio come il prodotto.
Più in generale, abbiamo allora bisogno di:
fissare un linguaggio \(L\) fatto di simboli di relazione, funzione e costante;
stabilire una sintassi che permetta di costruire (algoritmicamente) formule che possano essere dotate di significato e analizzate;
introdurre l’opportuna nozione di modello, ovvero di “realtà” in cui poter valutare le formule: questo vuol dire stabilire qual’è l’universo del discorso e attribuire un significato “concreto” agli oggetti di base, ovvero ai simboli del linguaggio \(L\);
introdurre opportune regole di interpretazione dei simboli logici che permettano di interpretare tutte le formule nel modello dato e decidere se siano vere o meno in tale contesto (relazione di soddisfazione \(\models\));
in questo modo, considerando tutti i possibili modelli si potrà nuovamente parlare di tautologia, contraddizione, soddisfacibilità e conseguenza logica (= validità di un ragionamento).
Sintassi
Fissiamo innanzitutto una lista di simboli logici e tipografici che useremo per scrivere termini e formule:
la parentesi aperta \((\) e la parentesi chiusa \()\);
i simboli \(\neg\), \(\wedge\), \(\vee\), \(\to\), \(\leftrightarrow\), \(\exists\), \(\forall\) e \(=\);
una lista infinita di simboli detti variabili
\(v_{0} , v_{1} , v_{2} , \dots\)
Le lettere \(x , y , z , \dots \), eventualmente decorate con apici o pedici, indicano una generica variabile \(v_{n}\); l’insieme delle variabili viene indicato con \(Vbl\).
Un linguaggio \(L\) del prim’ordine consiste dei seguenti oggetti:
simboli di costante \(c , d , e , \dots\);
simboli di funzione \(f , g , h , \dots\);
simboli di relazione (o predicato) \(P , Q , R, \dots\).
Ad ogni simbolo di funzione e di predicato è associato un numero intero positivo detto arietà del simbolo. I simboli di arietà \(1\), \(2\) e \(3\) si dicono, rispettivamente, simboli unari, binari e ternari. L’arietà di \(f\) o di \(P\) è indicata con \(ar ( f )\) e \(ar ( P )\).
\(Const\) è l’insieme dei simboli di costante, \(Func\) è l’insieme dei simboli di funzione e \(Rel\) è l’insieme dei simboli di relazione (del linguaggio \(L\)). Quindi \[L = Const \cup Func \cup Rel.\]
I seguenti sono alcuni esempi di linguaggi del prim’ordine:
\(L = \{ R, f,g,a,c \}\) dove \(a\) e \(c\) sono simboli di costante, \(f\) è un simbolo di funzione unaria, \(g\) è un simbolo di funzione binaria e \(R\) è un simbolo di relazione binaria.
\(L = \{ P \}\) dove \(P\) è un simbolo di relazione con \(ar(P) = 3\).
\(L = \{ f,g,b \}\) con \(f\) e \(g\) simboli di funzione tali che \(ar(f) = ar(g) = 1\) e \(b\) simbolo di costante.
\(L = \emptyset\).
\(L = \{ +, \cdot \}\) con \(+\) e \(\cdot\) simboli di funzione binari.
\(L = \{ *, \prec \}\) con \(*\) simbolo di funzione binario e \(\prec\) simbolo di relazione binario.